The present invention relates to vector quantization of a block of input signals.
The principle of vector quantization will be briefly described hereunder. Assume an input vector X=(x.sub.1, x.sub.2, . . . , x.sub.k) which consists of a block of input signals. Partition a K-dimensional signal space R.sup.k into a finite number of subspaces R.sub.1, R.sub.2, . . . , R.sub.N, and let Y=(y.sub.1, y.sub.2, . . . , y.sub.N) be a set of the representative points (e.g. the center of gravity) of the respective subspaces. Producing this representative point y.sub.i as an output vector corresponding to input vector X included in the specific subspace R.sub.i is referred to as vector quantization. Vector quantization Q is defined by the following formula: EQU Q:R.sup.k .fwdarw.Y
wherein ##EQU1##
The vector quantization Q can also be defined as the cascade connection of coding (C) and decoding (D). Coding C is the mapping of R.sup.k onto an index set J=(1, 2, . . . , N) for the output vector set Y=(y.sub.1, y.sub.2, . . . y.sub.N), whereas decoding D is the mapping of J onto Y. These relations are expressed as follows: EQU C:R.sup.k .fwdarw.J,D:J.fwdarw.Y,Q=D.multidot.C
In vector quantization, it is the coded output J that is transmitted or recorded.
Vector quantization achieves a particularly efficient quantization when the incoming signals have a certain correlation as in video or audio signals, or if the probability density of the amplitudes of the signals have some deviation. As a further advantage, data compression can be accomplished by transmitting or recording a coded output including fewer sets of output vectors.
The conventional quantizer of the type contemplated by the present invention relies on scalar quantization wherein individual input signal samples are quantized to corresponding output signal levels. A schematic diagram of the conventional scalar quantizer is shown in FIG. 1, wherein 1 represents a sequence of input signals x.sub.1, x.sub.2, . . . , x.sub.k (k is an integer), 2 is the scalar quantizer, and 3 is a sequence of output signals y.sub.1, y.sub.2, . . . y.sub.k produced by converting the respective sample of signal sequence 1 to corresponding quantized levels.
Suppose the amplitude probability density distribution of input pulses 1 describes a Gaussian curve with the origin positioned at the center. The conventional scalar quantizer for minimizing the distortion between the input signal sequence 1 and output signal sequence 2 has the characteristics shown in FIG. 2, where in the qnantized levels become coarser as they depart from the origin. However, if the respective sample of input signal sequence 1 are correlated to each other, the conventional technique of quantizing individual samples for providing minimum distortion does not assure optimum quantization of the output signal sequence.
In the conventional method of quantizing color video signals, samples from each of the red (R), green (G) and blue (B) channels are individually quantized in parallel with respect to each channel. FIG. 3 is a schematic representation of the conventional scalar quantizer for processing color video signals, wherein 201 is a sequence of input red video signals, 202 is a sequence of input green video signals, 203 is a sequence of input blue video signals, 204 is a scalar quantizer, 205 is a sequence of red video signals, 206 is a sequence of output green video signals, and 207 is a sequence of output blue video signals.
The scalar quantizers 204 quantize individual samples of R, G and B input signals in parallel with respect to each channel. To achieve good color balance among the three channels, uniform quantization characteristics are employed as shown in FIG. 4. However, adjacent samples from the same channel, or samples in the same picture element from two different channels are so closely correlated to each other that a considerable quantization loss occurs in the scalar quantizer of FIG. 3.
A specific probability model such as the AR model can be assumed for the a.c. component of a video or audio signal, but such model fitting is difficult for the d.c. component.
When the amplitude varies greatly, efficient coding cannot be realized by a fixed vector quantizer.
In the operation of the coder of the conventional vector quantizer, the distortion computing section provides a critical path for the overall processing efficiency. If the time required for computing the distortion between input and each output vector is expressed by td, the coding time t.sub.v for each sample is: EQU t.sub.v =N.multidot.td/K (sec/sample).
As described above, the conventional vector quantizer must make a full search of all elements of an output vector set with respect to the input vector in order to detect the least distorted output vector. Therefore, if the number of output vectors N is increased for the purpose of accomplishing high-fidelity vector quantization with minimum quantization noise, the processing time per sample is also proportionately increased.
Further, schematic representation of the conventional interframe coding apparatus of the type contemplated by the present invention is given in FIG. 5, wherein (a) is a coder and (b) is a decoder. In FIG. 5, 601 is an A/D converter, 602 is a subtractor 604 is a scalar quantizer, 605 is an adder, 603 is a frame memory and 612 is a D/A converter.
Suppose the f-th frame (f being an integer) is being raster-scanned from top to bottom and from left to right. The analog video signal 606 of that frame is digitized in the A/D converter 601. Here, sequence of samples of this digital video signal 607 is denoted by S.sub.t.sup.f (t being the number of the sample sequence under raster-scanning); a predictive signal 608 made from the sampled value S.sub.t.sup.f on the same position of the privious frame is denoted by P.sub.t.sup.f ; a signal 609 for the interframe difference between the video signal 607 and the predictive signal 608 is denoted by .epsilon..sub.t.sup.f ; a scalar quantized signal 610 per sample of the interframe differential signal 609 is denoted by .epsilon..sub.t.sup.f ; and a reproduced video signal 611 which is the sum of the scalar quantized signal 610 and the predictive signal 608 is denoted by S.sub.t.sup.f.
Given these signals, the coder of FIG. 5(a) performs the following operations: EQU .epsilon..sub.t.sup.f =S.sub.t.sup.f -P.sub.t.sup.f EQU .epsilon..sub.t.sup.f =.epsilon..sub.t.sup.f +q.sub.k.sup.f EQU S.sub.t.sup.f =P.sub.t.sup.f +.epsilon..sub.t.sup.f =S.sub.t.sup.f +q.sub.k.sup.f
wherein P.sub.t.sup.f =S.sub.t.sup.f .multidot.Z.sup.-f (Z.sup.-f indicating a one-frame delay), and q.sub.t.sup.f represents scalar quantization noise. As is clear from these formulas, the interframe differential signal .epsilon..sub.t.sup.f whose power is smaller than S.sub.t.sup.f because of the signal correlation is scalar-quantized to .epsilon..sub.t.sup.f by reducing the number of quantizing level so that the quantization noise is a minimum with respect to the amplitude probability distribution P(.epsilon..sub.k) of that differential signal. Proper codes may be assigned to the respective quantizing levels of .epsilon..sub.t.sup.f for high-efficiency coding and subsequent data transmission.
In the decoder of FIG. 5(b), the incoming scalar-quantized signal 610 is subjected to the operation S.sub.t.sup.f =P.sub.t.sup.f +.epsilon..sub.t.sup.f =S.sub.t.sup.f +q.sub.k.sup.f so as to provide a reproduced video signal 611 containing the quantization noise q.sub.t.sup.f.
As described above, in the conventional interframe coding apparatus, the signal indicating the difference between the video signal for the present frame and that for the previous frame at the same position is subjected to scalar quantization by reducing the number of quantizing levels per sample. However, because of the presence of Gaussian noise in the video signal, this method involves much difficulty in coding only the significant interframe differential signal that has been generated by the movement of the pictorial object. Furthermore, since scalar quantization is performed on each sample of the interframe differential signal, it is impossible to make the bit rate lower than a certain value.